#pragma once
#include<iostream>
#include<assert.h>

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREELIST = 208;

// 注意这里需要加引用
static void*& NextObj(void* obj)
{
	return (*(void**)obj);
}

class FreeList
{
public:
	void Push(void* obj)
	{
		// 头插
		assert(obj);
		NextObj(obj) = _freelist;
		_freelist = obj;
	}
	void* Pop()
	{
		// 头删
		void* obj = _freelist;
		_freelist = NextObj(obj);
		return obj;
	}
	bool Empty()
	{
		return _freelist == nullptr;
	}
private:
	void* _freelist = nullptr;
};

class SizeClass
{
public:
	static inline size_t _RoundUp(size_t bytes, size_t AlignNum)
	{
		// 1. 判断方式
		//if (bytes % AlignNum != 0)
		//{
		//	return (bytes / AlignNum + 1) * AlignNum;
		//}
		//else
		//{
		//	return bytes;
		//}

		// 2. 位运算方式 
		//                 开bytes       开16           开24
		// Bytes:          1 - 8         9 - 16         17 - 24
	    // AlignNum - 1:   7   7         7    7         7    7
		//                 8   15        16  23         24   31
		//Bytes+AlignNum-1:00001xxx      00010xxx       00100xxx
		//~(AlignNum - 1) :11111000      11111000       11111000
		//              (8)00001000  (16)00010000   (32)00100000
		return (bytes + AlignNum - 1) & ~(AlignNum - 1);
	}
	// 1. 对齐大小计算
	static inline size_t RoundUp(size_t bytes)
	{
		// 整体控制在最多10%左右的内碎片浪费
		// [1,128]               8byte对齐         freelist[0,16)
		// [128+1,1024]          16byte对齐        freelist[16,72)
		// [1024+1,8*1024]       128byte对齐       freelist[72,128)
		// [8*1024+1,64*1024]    1024byte对齐      freelist[128,184)
		// [64*1024+1,256*1024]  8*1024byte对齐    freelist[184,208)
		if (bytes <= 128)
		{
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024)
		{
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8 * 1024)
		{
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 64 * 1024)
		{
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256 * 1024)
		{
			return _RoundUp(bytes, 8*1024);
		}
		else
		{
			assert(false);
			return -1;
		}
	}

	// 1. 
	//size_t _Index(size_t bytes, size_t AlignNum)
	//{
	//	if (bytes % AlignNum == 0)
	//	{
	//		return bytes / AlignNum - 1;
	//	}
	//	else
	//	{
	//		return bytes / AlignNum;
	//	}
	//}

	// 2. 位运算方式 
	//                                                 开bytes       开16           开24
	//  Bytes:                                         1 - 8         9 - 16         17 - 24
    // (1<<align_shift)-1:                             7   7         7    7         7    7
	// (bytes + (1 << align_shift) - 1):               8   15        16  23         24   31
    //  右移  align_shift 再减 1       : 除8 再 减1    0   0         1    1         2    2    
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	// 2. 计算映射的哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1]
				+ group_array[0];
		}
		else if (bytes <= 256 * 1024){
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else
		{
			assert(false);
			return -1;
		}
	}
};